﻿using Newtonsoft.Json;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace leetcode_learning
{
    public class Bilibili
    {

        /// <summary>
        /// 两数之和 （O(N^2)）
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int[] TwoSum(int[] nums, int target)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                var a = nums[i];

                var b = target - a;

                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (b == nums[j])
                    {
                        return new int[] { i, j };
                    }
                }
            }

            return null;
        }

        /// <summary>
        /// 两数之和 （O(N)）
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int[] TwoSumHash(int[] nums, int target)
        {
            if (nums.Length < 2)
                throw new Exception();
            Dictionary<int, int> map = new Dictionary<int, int>();

            for (int i = 0; i < nums.Length; i++)
            {
                var a = nums[i];

                var b = target - a;
                if (map.ContainsKey(b))
                {
                    return new int[] { i, map.GetValueOrDefault(b) };
                }
                if (!map.ContainsKey(a))
                    map.Add(a, i);
            }

            return new int[] { };
        }

        /// <summary>
        /// 两数相加（递归版）
        /// </summary>
        /// <param name="l1"></param>
        /// <param name="l2"></param>
        /// <returns></returns>
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return singleNodeSum(new ListNode(), 0, l1, l2);
        }

        private ListNode singleNodeSum(ListNode node, int carry = 0, ListNode node1 = null, ListNode node2 = null)
        {
            if (node1 != null || node2 != null)
            {
                var a = node1 != null ? node1.val : 0;
                var b = node2 != null ? node2.val : 0;

                var sum = a + b + carry;

                node.val = sum % 10;

                if ((node1 != null && node1.next != null) || (node2 != null && node2.next != null))
                {
                    node.next = new ListNode();
                }
                node.next = singleNodeSum(node.next, sum / 10, node1 != null ? node1.next : null, node2 != null ? node2.next : null);

                return node;
            }
            else
            {
                if (carry > 0)
                {
                    return new ListNode(carry);
                }

                return null;
            }
        }

        /// <summary>
        /// 两数相加（while循环版）
        /// </summary>
        /// <param name="l1"></param>
        /// <param name="l2"></param>
        /// <returns></returns>
        public ListNode WhileNodeSum(ListNode l1 = null, ListNode l2 = null)
        {
            ListNode root = new ListNode(0);
            ListNode cursor = root;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0)
            {
                int l1Val = l1 != null ? l1.val : 0;
                int l2Val = l2 != null ? l2.val : 0;
                int sumVal = l1Val + l2Val + carry;
                carry = sumVal / 10;

                ListNode sumNode = new ListNode(sumVal % 10);
                cursor.next = sumNode;

                cursor = cursor.next; // 赋值转移

                if (l1 != null) l1 = l1.next;
                if (l2 != null) l2 = l2.next;
            }

            return root.next;
        }

        /// <summary>
        /// 二叉树的最大深度
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public int MaxDepth(TreeNode root)
        {
            if (root == null)
                return 0;
            int leftHeight = MaxDepth(root.left);
            int rightHeight = MaxDepth(root.right);
            return Math.Max(leftHeight, rightHeight) + 1;
        }

        /// <summary>
        /// 从前序与中序遍历序列构造二叉树
        /// </summary>
        /// <param name="preorder"></param>
        /// <param name="inorder"></param>
        /// <returns></returns>
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            //for (int i = 0; i < preorder.Length; i++)
            //{

            //}
            return new TreeNode();
        }

        /// <summary>
        /// 移动零 [0,1,0,3,12] 1 0 0 3 12
        /// </summary>
        /// <param name="nums"></param>
        public void MoveZeroes(int[] nums)
        {
            int j = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != 0)
                {
                    var a = nums[i];
                    nums[i] = nums[j];
                    nums[j++] = a;
                }
            }
        }

        /// <summary>
        /// 回文数
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public bool IsPalindrome(int x)
        {
            if (x < 0)
                return false;

            var num = x;
            var newnum = 0;
            while (num > 0)
            {
                newnum = newnum * 10 + num % 10;
                num = num / 10;
            }
            if (x == newnum)
                return true;
            else return false;
        }

        /// <summary>
        /// 合并两个有序链表
        /// </summary>
        /// <param name="list1"></param>
        /// <param name="list2"></param>
        /// <returns></returns>
        public ListNode MergeTwoLists(ListNode list1, ListNode list2)
        {
            if (list1 != null && list2 != null)
            {
                if (list1.val > list2.val)
                {
                    return new ListNode(list2.val, MergeTwoLists(list1, list2.next));
                }
                else
                {
                    return new ListNode(list1.val, MergeTwoLists(list1.next, list2));
                }
            }
            else
            {
                return list1 == null ? list2 : list1;
            }
        }

        /// <summary>
        /// 两个数组的交集 II
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int[] Intersect(int[] nums1, int[] nums2)
        {
            var map = new Dictionary<int, int>();
            for (int i = 0; i < nums1.Length; i++)
            {
                if (!map.ContainsKey(nums1[i]))
                    map.Add(nums1[i], 1);
                else
                    map[nums1[i]] += 1;
            }

            var list = new List<int>();
            for (int i = 0; i < nums2.Length; i++)
            {
                if (map.ContainsKey(nums2[i]))
                {
                    list.Add(nums2[i]);

                    if (map[nums2[i]] == 1)
                        map.Remove(nums2[i]);
                    else
                        map[nums2[i]] -= 1;
                }
            }
            var res = new int[list.Count];
            for (int i = 0; i < list.Count; i++)
            {
                res[i] = list[i];
            }

            return res;
        }

        /// <summary>
        /// 最大子数组和
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MaxSubArray(int[] nums)
        {
            int pre = 0, max = nums[0];
            foreach (var x in nums)
            {
                //if (pre + x > x)
                //    pre = pre + x;
                //else pre = x;
                pre = Math.Max(pre + x, x);

                //if (max < pre)
                //    max = pre;
                max = Math.Max(pre, max);
            }

            return max;
        }

        /// <summary>
        /// 有效的括号
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public bool IsValid(string s)
        {
            var stack = new Stack<string>();
            for (int i = 0; i < s.Length; i++)
            {
                var str = s.Substring(i, 1);
                if (stack.Count > 0 && (str == "}" || str == "]" || str == ")"))
                {
                    var dstr = stack.Peek();
                    if ((str == "}" && dstr == "{") ||
                        (str == "]" && dstr == "[") ||
                        (str == ")" && dstr == "("))
                    {
                        stack.Pop();
                        continue;
                    }
                    else return false;
                }
                stack.Push(str);

            }
            return stack.Count == 0;
        }

        /// <summary>
        /// 爬楼梯 （斐波那契数列）
        /// 1、动态规划
        /// 2、矩阵快速幂
        /// 3、通项公式
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int ClimbStairs(int n)
        {
            int p = 0, q = 0, r = 1;
            for (int i = 1; i <= n; ++i)
            {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }

        /// <summary>
        /// 买卖股票的最佳时机
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            //for (int i = 0; i < prices.Length; i++)
            //{
            //    for (int j = i + 1; j < prices.Length; j++)
            //    {
            //        if (prices[i] < prices[j] && ((prices[j] - prices[i]) > max))
            //        {
            //            max = prices[j] - prices[i];
            //        }
            //    }
            //}

            //int a = 0, b = 1, max = 0;
            //while (a < prices.Length - 1)
            //{
            //    if (b > prices.Length - 1)
            //    {
            //        ++a;
            //        b = a + 1;
            //        continue;
            //    }
            //    var p1 = prices[a];
            //    var p2 = prices[b];

            //    if (p1 > p2)
            //    {
            //        ++a;
            //        b = a + 1;
            //        continue;
            //    }
            //    max = Math.Max(p2 - p1, max);
            //    ++b;
            //}
            int minprice = prices[0];
            int max = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                if (prices[i] < minprice)
                {
                    minprice = prices[i];
                }
                else if (prices[i] - minprice > max)
                {
                    max = prices[i] - minprice;
                }
            }
            return max;
        }

        /// <summary>
        /// 最小的k个数
        /// 1、排序（快排）
        /// 2、大顶堆
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int[] GetLeastNumbers(int[] arr, int k)
        {
            var res = new int[k];
            Array.Sort(arr);
            for (int i = 0; i < k; i++)
            {
                res[i] = arr[i];
            }

            return res;
        }

        /// <summary>
        /// 斐波那契数列
        /// 1、动态规划
        /// 2、矩阵快速幂
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int Fib(int n)
        {
            //if (n == 0)
            //    return 0;
            //if (n == 1)
            //    return 1;
            //if (n == 2)
            //    return 1;
            //return Fib(n - 1) + Fib(n - 2);

            const int MOD = 1000000007;//1e9+7
            if (n < 2)
            {
                return n;
            }
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n; ++i)
            {
                p = q;
                q = r;
                r = (p + q) % MOD;
            }
            return r;
        }

        /// <summary>
        /// 环形链表
        /// 1、哈希表
        /// 2、快慢指针
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public bool HasCycle(ListNode head)
        {
            //var dic = new Dictionary<ListNode, int>();
            //var node = head;

            //while (node != null)
            //{
            //    if (!dic.ContainsKey(node))
            //    {
            //        dic.Add(node, 1);
            //        node = node.next;
            //    }
            //    else return true;
            //}

            //return false;

            //ListNode node1 = head, node2 = head;

            //while (node1 != null && node2 != null)
            //{
            //    node1 = node1.next;
            //    if (node2.next != null)
            //        node2 = node2.next.next;
            //    else break;

            //    if (node1 == node2)
            //        return true;                
            //}
            //return false;

            if (head == null || head.next == null)
            {
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast)
            {
                if (fast == null || fast.next == null)
                {
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }

        /// <summary>
        /// 不用加减乘除做加法
        /// 位运算
        /// 无进位和+进位
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public int Add(int a, int b)
        {
            while (b != 0)
            { // 当进位为 0 时跳出
                int d = a & b;
                int c = d << 1;  // c = 进位
                a ^= b; // a = 非进位和
                b = c; // b = 进位
            }
            return a;
        }

        /// <summary>
        /// 连续子数组的最大和
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MaxSubArray2(int[] nums)
        {
            int max = nums[0], pre = 0;
            foreach (var x in nums)
            {
                pre = Math.Max(pre + x, x);
                max = Math.Max(pre, max);
            }
            return max;
        }

        /// <summary>
        /// Excel 表列序号
        /// </summary>
        /// <param name="columnTitle"></param>
        /// <returns></returns>
        public int TitleToNumber(string columnTitle)
        {
            int total = 0;
            var word = columnTitle;
            while (word.Length > 0)
            {
                var f = word.Substring(0, 1);
                if (word.Length != 1)
                    total += (Encoding.ASCII.GetBytes(f)[0] - 64) * Convert.ToInt32(Math.Pow(26, word.Length - 1));
                else
                    total += Encoding.ASCII.GetBytes(f)[0] - 64;
                word = word.Remove(0, 1);
            }
            return total;
        }

        /// <summary>
        /// 顺时针打印矩阵
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public int[] SpiralOrder(int[][] matrix)
        {
            if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
            {
                return new int[0];
            }
            int rows = matrix.Length, columns = matrix[0].Length;
            int[] order = new int[rows * columns];
            int index = 0;
            int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
            while (left <= right && top <= bottom)
            {
                for (int column = left; column <= right; column++)
                {
                    order[index++] = matrix[top][column];
                }
                for (int row = top + 1; row <= bottom; row++)
                {
                    order[index++] = matrix[row][right];
                }
                if (left < right && top < bottom)
                {
                    for (int column = right - 1; column > left; column--)
                    {
                        order[index++] = matrix[bottom][column];
                    }
                    for (int row = bottom; row > top; row--)
                    {
                        order[index++] = matrix[row][left];
                    }
                }
                left++;
                right--;
                top++;
                bottom--;
            }
            return order;
        }

        /// <summary>
        /// 合并两个有序数组
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="m"></param>
        /// <param name="nums2"></param>
        /// <param name="n"></param>
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            if (n == 0)
                return;
            //int a = 0, b = 0;
            //while (a < m + n)
            //{
            //    if (a >= m)
            //    {
            //        for (int i = 0; i < n; i++)
            //            nums1[a++] = nums2[i];
            //        break;
            //    }
            //    else if (nums1[a] > nums2[b])
            //    {
            //        var c = nums1[a];
            //        nums1[a++] = nums2[b];
            //        nums2[b] = c;

            //        Array.Sort(nums2);
            //        continue;
            //    }
            //    a++;
            //}

            for (int i = m; i < m + n; i++)
            {
                nums1[i] = nums2[i - m];
            }
            Array.Sort(nums1);
        }

        /// <summary>
        /// 反转链表
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode ReverseList(ListNode head)
        {
            //var stack = new Stack();

            //var node = head;
            //while (node != null)
            //{
            //    stack.Push(node.val);
            //    node = node.next;
            //}

            //return Out(stack);

            if (head == null || head.next == null)
            {
                return head;
            }
            ListNode newHead = ReverseList(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }

        private ListNode Out(Stack stack)
        {
            var node = new ListNode();
            if (stack.Count > 0)
            {
                node.val = (int)stack.Pop();
                node.next = Out(stack);
                return node;
            }
            else
                return null;
        }

        /// <summary>
        /// 反转链表
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode ReverseListDictionary(ListNode head)
        {
            var dic = new Dictionary<int, int>();

            var node = head;
            int i = 0;
            while (node != null)
            {
                dic.Add(i++, node.val);
                node = node.next;
            }

            return OutDictionary(dic);
        }

        private ListNode OutDictionary(Dictionary<int, int> dic)
        {
            var node = new ListNode();
            if (dic.Count > 0)
            {
                node.val = dic[dic.Count - 1];
                dic.Remove(dic.Count - 1);
                node.next = OutDictionary(dic);
                return node;
            }
            else return null;
        }

        /// <summary>
        /// 实现strStr()
        /// </summary>
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public int StrStr(string haystack, string needle)
        {
            if (string.IsNullOrEmpty(needle))
                return 0;
            int first = -1;

            for (int i = 0; i < haystack.Length; i++)
            {
                if (i + needle.Length <= haystack.Length)
                {
                    var s = haystack.Substring(i, needle.Length);
                    if (s == needle)
                    {
                        first = i;
                        break;
                    }
                }
                else break;
            }

            return first;
        }

        /// <summary>
        /// 链表中倒数第k个节点
        /// </summary>
        /// <param name="head"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public ListNode GetKthFromEnd(ListNode head, int k)
        {
            int deep = 0;
            ListNode node = head;
            ListNode result = head;
            while (node != null)
            {
                node = node.next;
                deep++;
            }

            int num = 0;
            while (num < deep - k)
            {
                result = result.next;
                num++;
            }

            return result;
        }

        public ListNode ReverseListT(ListNode head)
        {
            if (head == null || head.next == null)
                return head;

            ListNode newnode = ReverseListT(head.next);
            head.next.next = head;
            head.next = null;
            return newnode;
        }

        public int BreakfastNumber(int[] staple, int[] drinks, int x)
        {
            double MOD = 1e9 + 7;
            double ret = 0;
            int n = staple.Length, right_pointer = drinks.Length - 1;
            Array.Sort(staple);
            Array.Sort(drinks);
            //for (int i = 0; i < n; i++)
            //{
            //    int left_pointer = 0, right_pointer = m - 1;
            //    while (left_pointer <= right_pointer)
            //    {
            //        int middle_pointer = (left_pointer + right_pointer) / 2;   //二分搜索 
            //        if (staple[i] + drinks[middle_pointer] <= x) left_pointer = middle_pointer + 1;
            //        else right_pointer = middle_pointer - 1;
            //    }
            //    ret += right_pointer + 1;
            //    ret %= MOD;
            //}
            //return (int)ret;

            for (int i = 0; i < n; i++)
            {
                while (right_pointer >= 0)
                {
                    if (staple[i] + drinks[right_pointer] <= x)
                    {
                        ret += right_pointer + 1;
                        ret %= MOD;
                        break;
                    }
                    else right_pointer--;
                }
            }
            return (int)ret;
        }

        /// <summary>
        /// 相交链表
        /// </summary>
        /// <param name="headA"></param>
        /// <param name="headB"></param>
        /// <returns></returns>
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            var ha = headA;
            HashSet<ListNode> dic = new HashSet<ListNode>();

            while (ha != null)
            {
                Console.WriteLine(JsonConvert.SerializeObject(ha));
                dic.Add(ha);
                ha = ha.next;
            }
            ha = headB;
            while (ha != null)
            {
                if (dic.Contains(ha))
                    break;
                ha = ha.next;
            }

            return ha;
        }


        public string ComplexNumberMultiply(string num1, string num2)
        {
            var a = num1.Split('+');

            var b = num2.Split('+');

            var a0 = int.Parse(a[0]);
            var b0 = int.Parse(b[0]);

            var a1 = int.Parse(a[1].Replace("i", ""));
            var b1 = int.Parse(b[1].Replace("i", ""));

            return ((a0 * b0 - a1 * b1) == 0 ? "0+" : (a0 * b0 - a1 * b1).ToString() + "+") + (a0 * b1 + b0 * a1).ToString() + "i";
        }

        public int FindKthLargest(int[] nums, int k)
        {
            Array.Sort(nums);
            return nums[nums.Length - k];
        }

        public int[] TopKFrequent(int[] nums, int k)
        {
            var dic = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (dic.ContainsKey(nums[i]))
                    dic[nums[i]] = dic[nums[i]] + 1;
                else
                    dic.Add(nums[i], 1);
            }
            int mindex = 0;
            var maxs = new int[dic.Count];
            foreach (var item in dic)
            {
                maxs[mindex++] = item.Value;
            }
            Array.Sort(maxs);

            var result = new int[k];

            for (int i = 0; i < k; i++)
            {
                foreach (var item in dic)
                {
                    if (item.Value == maxs[maxs.Length - 1 - i])
                    {
                        result[i] = item.Key;
                        dic.Remove(item.Key);
                        break;
                    }
                }
            }

            return result;
        }

        public int MaxSubArrayX(int[] nums)
        {
            int max = nums[0], pre = nums[0];

            int index = 0;
            while (index < nums.Length)
            {
                pre = Math.Max(pre + nums[index], nums[index]);
                max = Math.Max(max, pre);

                index++;
            }
            return max;
        }

        public string LargestNumber(int[] nums)
        {
            if (nums.Length == 1)
                return nums[0].ToString();

            string[] snums = new string[nums.Length];
            for (int i = 0; i < nums.Length; i++)
            {
                snums[i] = nums[i].ToString();
            }

            Array.Sort(snums);

            for (int i = 0; i + 1 < snums.Length; i++)
            {
                if (snums[i + 1].StartsWith(snums[i]) && CompartString(snums[i], snums[i + 1]))
                {
                    var c = snums[i];
                    snums[i] = snums[i + 1];
                    snums[i + 1] = c;
                }
            }

            var result = "";

            for (int i = snums.Length; i > 0; i--)
            {
                result += snums[i - 1];
            }

            return result.Replace("0", "");
        }

        private bool CompartString(string s1, string s2)
        {
            var s = long.Parse(s1 + s2);
            var n = long.Parse(s2 + s1);
            return s > n;
        }


        public int RomanToInt(string s)
        {
            Dictionary<char, int> symbolValues = new Dictionary<char, int> {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

            int ans = 0;
            int n = s.Length;
            for (int i = 0; i < n; ++i)
            {
                int value = symbolValues[s[i]];
                if (i < n - 1 && value < symbolValues[s[i + 1]])
                {
                    ans -= value;
                }
                else
                {
                    ans += value;
                }
            }
            return ans;
        }
    }
}
